home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / MacHaskell 2.2 / progs / demo / queens.hs < prev    next >
Encoding:
Text File  |  1994-09-27  |  986 b   |  38 lines  |  [TEXT/YHS2]
  1. {- This is the n Queens problem. -}
  2.  
  3. module Main where
  4.  
  5. queens :: Int -> [[Int]]
  6. queens size  = queens' size size
  7.  
  8. queens' :: Int -> Int -> [[Int]]
  9. queens' 0     _    = [[]]
  10. queens' (n+1) size = [q:qs | qs <- queens' n size, q <- [1..size],
  11.                  not (threatens q qs)]
  12.  
  13. threatens :: Int -> [Int] -> Bool
  14. threatens q qs = q `elem` qs || q `elem` (diagonals 1 qs)
  15.  
  16. diagonals :: Int -> [Int] -> [Int]
  17. diagonals _  []    = []
  18. diagonals n (q:qs) = (q+n) : (q-n) : diagonals (n+1) qs
  19.  
  20. main = putStr "Enter board size: " >>
  21.        getLine >>= \line1 -> 
  22.        let size = read line1 in
  23.         putStr "Number of solutions: " >>
  24.         getLine >>= \line2 ->
  25.         putStr (concat (map (\x -> showBoard size x)
  26.                         (take (read line2) (queens size))))
  27.  
  28. showBoard :: Int -> [Int] -> String
  29.  
  30. showBoard size pos =
  31.   concat (map showRow pos) ++ "\n"
  32.     where
  33.       showRow n = concat [if i == n then "Q " else ". " | i <- [1..size]]
  34.                   ++ "\n"
  35.                 
  36.  
  37.  
  38.